Initial Population

The initial population is generated with the Nearest Neighbor heuristic starting once with each city.

Nearest Neighbor heuristic: Every time, go to the nearest city from current one if its not already visited.

This gives a decently naive but valid solution to the problem. Start with each city and keep applying this heuristic until all cities are visted and you have come back to the starting city.

For n cities, you get an initial population of n tours.

Code snippet

def nearest_neighbor_tsp(distances, s):
    num_cities = len(distances)
    unvisited = set(range(num_cities))
    tour = []
    current_city = s

    while unvisited:
        unvisited.remove(current_city)
        tour.append(current_city)
        if unvisited:
            nearest_neighbor = min(unvisited, key=lambda city: distances[current_city][city])
        current_city = nearest_neighbor
    return tour